Given an m x n binary matrix mat, return the length of the longest line of consecutive one in the matrix.
The line could be horizontal, vertical, diagonal, or anti-diagonal.
Example 1:
Input: mat = [[0,1,1,0],[0,1,1,0],[0,0,0,1]] Output: 3
Example 2:
Input: mat = [[1,1,1,1],[0,1,1,0],[0,0,0,1]] Output: 4
Constraints:
m == mat.lengthn == mat[i].length1 <= m, n <= 1041 <= m * n <= 104mat[i][j]is either0or1.
Average Rating: 4.08 (26 votes)
Solution
Approach 1: Brute Force
Algorithm
The brute force approach is really simple. We directly traverse along every valid line in the given matrix: i.e. Horizontal, Vertical, Diagonal aline above and below the middle diagonal, Anti-diagonal line above and below the middle anti-diagonal. Each time during the traversal, we keep on incrementing the count if we encounter continuous 1's. We reset the count for any discontinuity encountered. While doing this, we also keep a track of the maximum count found so far.
Complexity Analysis
Let m be the length of the matrix and n be the width of the matrix. As a result, mn would be the total number of cells in the matrix.
- Time complexity : O(mn). We traverse along the entire matrix 4 times.
- Space complexity : O(1). Constant space is used.
Approach 2: Using 3D Dynamic Programming
Algorithm
Instead of traversing over the same matrix multiple times, we can keep a track of the 1' along all the lines possible while traversing the matrix once only. In order to do so, we make use of a 4mn sized dp array. Here, dp[0], dp[1], dp[2] ,dp[3] are used to store the maximum number of continuous 1's found so far along the Horizontal, Vertical, Diagonal and Anti-diagonal lines respectively. e.g. dp[i][j][0] is used to store the number of continuous 1's found so far(till we reach the element M[i][j]), along the horizontal lines only.
Thus, we traverse the matrix M in a row-wise fashion only but, keep updating the entries for every dp appropriately.
The following image shows the filled dp values for this matrix:
0 1 1 0
0 1 1 0
0 0 1 1
While filling up the dp, we can keep a track of the length of the longest consecutive line of 1's.
Watch this animation for complete process:
Complexity Analysis
-
Time complexity : O(mn). We traverse the entire matrix once only.
-
Space complexity : O(mn). dp array of size 4mn is used, where m and n are the number of rows ans coloumns of the matrix.
Approach 3: Using 2D Dynamic Programming
Algorithm
In the previous approach, we can observe that the current dp entry is dependent only on the entries of the just previous corresponding dp row. Thus, instead of maintaining a 2-D dp matrix for each kind of line of 1's possible, we can use a 1-d array for each one of them, and update the corresponding entries in the same row during each row's traversal. Taking this into account, the previous 3-D dp matrix shrinks to a 2-D dp matrix now. The rest of the procedure remains same as the previous approach.
Complexity Analysis
-
Time complexity : O(mn). The entire matrix is traversed once only.
-
Space complexity : O(n). dp array of size 4n is used, where n is the number of columns of the matrix.
Here is O(nm) solution by just using hash tables:
import collections
class Solution:
def longestLine(self, M: List[List[int]]) -> int:
row = collections.defaultdict(int)
col = collections.defaultdict(int)
ad = collections.defaultdict(int) # Ascending diagonal
dd = collections.defaultdict(int) # Descending diagonal
mx = 0
for i in range(len(M)):
for j in range(len(M[0])):
if not M[i][j]:
row[i] = col[j] = ad[j + i] = dd [j - i] = 0
else:
row[i] += 1
col[j] += 1
ad[j + i] += 1
dd[j - i] += 1
mx = max(mx, row[i], col[j], ad[j+i], dd[j-i])
return mx
The Brute Force is giving better complexity than you Dynamic Programming approaches. Why should I solve the Dynamic programming approach over the brute force (technically)?
April 26, 2017 2:23 AM
Could you add a comment on how the old/prev work to handle the diagonal case?
February 12, 2019 11:58 PM
the explaination for the third one is poor to understand
Why isnt this tagged DP if your solution is DP ? The array tag is practically useless on this platform
March 30, 2020 5:12 PM
Shouldn't approach 2 the same as approach 1 in term of time complexity?
You are going over the entire matrix once but at each element you are doing 4 times the amount of work compared to when you are going over an element in approach 1.
There is no need to create an entire MxN matrix with the dynamic programming solution. You only need to keep the values from the previous row and the current row. You also only need three values (horizontal can be tracked using a single variable). Space is therefore only dependent on the size of a single row with 23N values (2 rows, 3 values per column).
Very easy constant space solution with explanation:
https://leetcode.com/problems/longest-line-of-consecutive-one-in-matrix/discuss/176478/O(mn)-with-O(1)-space-with-detailed-explanation
October 18, 2018 4:24 AM
It took me some while to understand the old and prev variables. Excellent optimized dp solution.
There is a O(mn) time O(1) space solution as well. check this out
https://discuss.leetcode.com/topic/87416/o-mn-time-no-extra-space-solution
Time Submitted | Status | Runtime | Memory | Language |
|---|---|---|---|---|
| 05/26/2021 19:35 | Accepted | 96 ms | 39.5 MB | cpp |
xxxxxxxxxxclass Solution {public: int longestLine(vector<vector<int>>& mat) { int m = mat.size(), n = mat[0].size(); int res = 0; vector<vector<vector<int>>> dp(m, vector<vector<int>>(n, vector<int>(4, 0))); for(int i=0;i<m;i++) { for(int j=0;j<n;j++) { if(mat[i][j] == 1) { res = max(res, dp[i][j][0] = 1 + (j ? dp[i][j-1][0] : 0)); // horizontal res = max(res, dp[i][j][1] = 1 + (i ? dp[i-1][j][1] : 0)); // vertical res = max(res, dp[i][j][2] = 1 + (i&&j ? dp[i-1][j-1][2] : 0)); // diagonal res = max(res, dp[i][j][3] = 1 + (i&&j<n-1 ? dp[i-1][j+1][3] : 0)); // anti-diagonal } } } return res; }};